{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "# Try to Prove Goldbach's  Conjecture\n",
    "Cody Luo(cody@ustc.edu)  2019-08-27 2019-09-01 2019-09-02 \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "Abstract:\n",
    "**Goldbach Conjecture Inequality 1**: **`gold(n) < prime_pi(n)+sigma(n,0)`**  \n",
    "gold(n): the min non-negative integer makes that both `n-g` and `n+g` are primes  \n",
    "prime_pi(n): the count of primes in 1..n  \n",
    "sigma(n,0): the count of n.divisors()  \n",
    "\n",
    "`gold(n) < prime_pi(n), while n>344`\n",
    "`gold(n) < prime_pi(n)*4395/3449751 ≈ prime_pi(n)*0.0013, while n>57989356`\n",
    "\n",
    "**Goldbach Conjecture Inequality 2**: **`gold(n) < prime_pi(prime_pi(n)+n)`**\n",
    "\n",
    "Keywords: Goldbach Conjecture; Prime Gap Inequality; prime_pi(n); sigma(n,0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "**Improved Goldbach's Conjecture**  : Except `n=344; n=22,46; n=28`,for  any other positive integer `n>1`,there exists `g, 0=<g<prime_pi(n)`, make that both `n-g` and `n+g` are primes.\n",
    "As `n` increase from 2 to a very big integer, the peaks of gold(n) appear more and more slowly. `n>344, history_peak(gold(n))/prime_pi(n)` rapidly decreasing from `75/68 (n=344)` to `300/685 (n=5131)`,`1794/189274\n",
    " (n=2591107)`, `4395/3449751(n=57989356)`, ..., to a decimal approaching 0. `limit(sup gold(n)/prime_pi(n),n,+oo) == 0`\n",
    "\n",
    "Define `g:=gold(n)` as the min non-negative integer makes that both `n-g` and `n+g` are primes. so that `2*n=(n-g)+(n+g)=p+q`.\n",
    "\n",
    "(gold(n),prime_pi(n),prime_pi(prime_pi(n)+n),n)\n",
    "(75,68,80, 344)\n",
    "([9], 8, 10, 22)\n",
    "([9], 9, 12, 28)\n",
    "([15], 14,17, 46)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[([0], 1, 2), ([0], 2, 3), ([1], 2, 4), ([0, 2], 3, 5), ([1], 3, 6), ([0, 4], 4, 7), ([3, 5], 4, 8), ([2, 4], 4, 9), ([3], 4, 10), ([0, 6], 5, 11), ([1, 5], 5, 12), ([0, 6], 6, 13), ([3], 6, 14), ([2, 4], 6, 15), ([3], 6, 16), ([0, 6], 7, 17), ([1, 5], 7, 18), ([0], 8, 19), ([3, 9], 8, 20), ([2, 8], 8, 21), ([9], 8, 22), ([0, 6], 9, 23), ([5, 7], 9, 24), ([6], 9, 25), ([3], 9, 26), ([4, 10], 9, 27), ([9], 9, 28), ([0], 10, 29), ([1, 7, 11], 10, 30), ([0, 12], 11, 31), ([9], 11, 32), ([4, 10], 11, 33), ([3], 11, 34), ([6, 12], 11, 35), ([5, 7], 11, 36), ([0, 6], 12, 37), ([9], 12, 38), ([2, 8], 12, 39), ([3], 12, 40), ([0, 12], 13, 41), ([1, 5, 11], 13, 42), ([0], 14, 43), ([3, 15], 14, 44), ([2, 8, 14], 14, 45), ([15], 14, 46), ([0, 6], 15, 47), ([5, 11], 15, 48), ([12], 15, 49), ([3, 9], 15, 50), ([8, 10], 15, 51), ([9, 15], 15, 52), ([0, 6], 16, 53), ([7, 13, 17], 16, 54), ([12], 16, 55), ([3, 15], 16, 56), ([4, 10, 14, 16], 16, 57), ([15], 16, 58), ([0, 12], 17, 59), ([1, 7, 13], 17, 60), ([0, 18], 18, 61), ([9], 18, 62), ([4, 10, 16], 18, 63), ([3], 18, 64), ([6, 18], 18, 65), ([5, 7, 13], 18, 66), ([0, 6], 19, 67), ([15], 19, 68), ([2, 10], 19, 69), ([3, 9], 19, 70), ([0, 12, 18], 20, 71), ([1, 11], 20, 72), ([0, 6], 21, 73), ([15], 21, 74), ([4, 8, 14, 22], 21, 75), ([3], 21, 76), ([6], 21, 77), ([5, 11, 19], 21, 78), ([0, 18], 22, 79), ([9, 21], 22, 80), ([2, 8, 20, 22], 22, 81), ([15, 21], 22, 82), ([0, 24], 23, 83), ([5, 13, 17, 23], 23, 84), ([12, 18, 24], 23, 85), ([3, 15], 23, 86), ([14, 16, 20], 23, 87), ([9, 15, 21], 23, 88), ([0, 18], 24, 89), ([7, 11, 17, 19, 23], 24, 90), ([12, 18], 24, 91), ([9, 21], 24, 92), ([4, 10, 14, 20], 24, 93), ([15], 24, 94), ([6, 12], 24, 95), ([7, 13, 17], 24, 96), ([0], 25, 97), ([9, 15], 25, 98), ([2, 10], 25, 99), ([3], 25, 100), ([0, 12], 26, 101), ([1, 5], 26, 102), ([0, 6, 24], 27, 103), ([3], 27, 104), ([2, 4, 8, 22, 26], 27, 105), ([3], 27, 106), ([0, 6, 24], 28, 107), ([1, 5, 19, 29], 28, 108), ([0, 30], 29, 109), ([3, 21, 27], 29, 110), ([2, 28], 29, 111), ([15], 29, 112), ([0, 24], 30, 113), ([13, 17, 25], 30, 114), ([12], 30, 115), ([15], 30, 116), ([10, 14, 20], 30, 117), ([9, 21], 30, 118), ([12, 18, 30], 30, 119), ([7, 11, 17, 19, 31], 30, 120), ([18], 30, 121), ([9, 15], 30, 122), ([14, 16, 26], 30, 123), ([15, 27], 30, 124), ([12, 24], 30, 125), ([13, 23, 25], 30, 126), ([0, 24, 30], 31, 127), ([21], 31, 128), ([2, 20, 22, 28], 31, 129), ([21, 27], 31, 130), ([0, 18], 32, 131), ([5, 19, 25, 31], 32, 132), ([6, 24, 30], 32, 133), ([3, 33], 32, 134), ([4, 22, 28, 32], 32, 135), ([27], 32, 136), ([0, 30], 33, 137), ([1, 11, 25, 29], 33, 138), ([0, 12], 34, 139), ([9, 27, 33], 34, 140), ([10, 32], 34, 141), ([15], 34, 142), ([6, 30], 34, 143), ([5, 7, 13, 35], 34, 144), ([6, 18], 34, 145), ([33], 34, 146), ([10, 16, 20, 34], 34, 147), ([9], 34, 148), ([0, 18], 35, 149), ([1, 13, 23], 35, 150), ([0, 12], 36, 151), ([15, 21], 36, 152), ([4, 14, 26], 36, 153), ([3, 27], 36, 154), ([18, 24], 36, 155), ([7, 17, 25], 36, 156), ([0, 6], 37, 157), ([9, 21], 37, 158), ([8, 20, 22, 32], 37, 159), ([3, 21, 33], 37, 160), ([12, 30], 37, 161), ([5, 11, 31, 35], 37, 162), ([0, 36], 38, 163), ([15, 27, 33], 38, 164), ([2, 8, 14, 16, 26, 28, 34], 38, 165), ([15, 27], 38, 166), ([0, 30], 39, 167), ([5, 11, 29, 31], 39, 168), ([12, 30], 39, 169), ([3, 21], 39, 170), ([8, 20, 22, 40], 39, 171), ([9, 21], 39, 172), ([0, 6, 24], 40, 173), ([7, 17, 23, 25, 37], 40, 174), ([18, 24, 36], 40, 175), ([3], 40, 176), ([4, 14, 20], 40, 177), ([15, 21], 40, 178), ([0, 12], 41, 179), ([1, 13, 17, 31], 41, 180), ([0, 18, 30, 42], 42, 181), ([9, 15], 42, 182), ([10, 16], 42, 183), ([27], 42, 184), ([6, 12], 42, 185), ([5, 7, 13, 37], 42, 186), ([6, 24, 36], 42, 187), ([9, 39], 42, 188), ([8, 10, 22, 38, 40], 42, 189), ([9, 33, 39], 42, 190), ([0, 42], 43, 191), ([1, 19, 35, 41], 43, 192), ([0, 30, 36], 44, 193), ([3, 45], 44, 194), ([2, 4, 16, 28, 32, 38, 44], 44, 195), ([3, 15, 33, 45], 44, 196), ([0, 30], 45, 197), ([1, 25, 31, 35, 41], 45, 198), ([0, 42], 46, 199), ([27, 33], 46, 200), ([10, 22, 28, 38], 46, 201), ([9, 21, 39], 46, 202), ([24, 30, 36], 46, 203), ([7, 23, 25, 37, 47], 46, 204), ([6, 24], 46, 205), ([27, 33], 46, 206), ([16, 26, 34, 44], 46, 207), ([15], 46, 208), ([18, 30, 42], 46, 209), ([13, 17, 19, 29, 31, 47], 46, 210), ([0, 12, 18, 30], 47, 211), ([15, 21, 39, 45], 47, 212), ([14, 16, 20], 47, 213), ([15], 47, 214), ([18, 24, 36, 42, 48], 47, 215), ([17, 23, 25, 35], 47, 216), ([6, 24], 47, 217), ([21, 39, 45], 47, 218), ([8, 20, 22, 38], 47, 219), ([9, 21], 47, 220), ([30, 42, 48], 47, 221), ([11, 29, 41], 47, 222), ([0], 48, 223), ([27, 33, 45], 48, 224), ([2, 14, 26, 32, 44, 46], 48, 225), ([3, 15, 45], 48, 226), ([0, 30, 36], 49, 227), ([1, 5, 29, 35, 49], 49, 228), ([0, 48], 50, 229), ([3, 33, 39, 51], 50, 230), ([2, 8, 20, 32, 38, 40, 50], 50, 231), ([9, 39, 51], 50, 232), ([0, 6, 36], 51, 233), ([5, 7, 23, 35, 37, 43], 51, 234), ([6, 36, 42], 51, 235), ([3, 45], 51, 236), ([4, 14, 26, 40, 44, 46], 51, 237), ([39, 45], 51, 238), ([0, 12, 42], 52, 239), ([1, 11, 17, 29, 41, 43], 52, 240), ([0, 30, 42], 53, 241), ([9, 15, 51], 53, 242), ([14, 20, 50], 53, 243), ([33], 53, 244), ([6, 12, 18, 48], 53, 245), ([5, 17, 23, 35, 47], 53, 246), ([24, 36], 53, 247), ([9, 15, 21], 53, 248), ([8, 20, 22], 53, 249), ([21, 27], 53, 250), ([0, 12, 18], 54, 251), ([11, 19, 25, 29, 41, 55], 54, 252), ([24, 30, 54], 54, 253), ([3, 15, 27], 54, 254), ([14, 16, 22, 26, 28], 54, 255), ([15, 27], 54, 256), ([0, 6, 24], 55, 257), ([19, 25, 35], 55, 258), ([18, 48], 55, 259), ([3, 9, 21, 33], 55, 260), ([10, 20, 22, 32, 50], 55, 261), ([21, 51], 55, 262), ([0, 6, 30], 56, 263), ([7, 13, 53], 56, 264), ([42], 56, 265), ([3, 15, 27], 56, 266), ([4, 10, 16, 26, 40, 44], 56, 267), ([39, 45], 56, 268), ([0, 12, 42], 57, 269), ([1, 7, 13, 37, 41, 43, 47], 57, 270), ([0, 42], 58, 271), ([9, 21, 39, 45], 58, 272), ([4, 10, 34, 40, 44], 58, 273), ([3, 33], 58, 274), ([6, 18, 36, 42], 58, 275), ([5, 7, 35, 37], 58, 276), ([0, 6, 36, 54], 59, 277), ([15, 39], 59, 278), ([2, 28, 38, 52], 59, 279), ([3, 51, 57], 59, 280), ([0, 12, 30], 60, 281), ([1, 11, 25, 31, 49, 55], 60, 282), ([0, 54], 61, 283), ([27, 33], 61, 284), ([8, 22, 28, 46, 52, 62], 61, 285), ([45], 61, 286), ([6, 24, 30, 60], 61, 287), ([5, 19, 25, 49, 59, 61], 61, 288), ([18, 48, 60], 61, 289), ([21, 27, 57], 61, 290), ([20, 22, 40, 58, 62], 61, 291), ([15, 21], 61, 292), ([0, 24, 54, 60], 62, 293), ([13, 17, 23, 37, 43, 53, 55], 62, 294), ([12, 18, 54], 62, 295), ([15, 57, 63], 62, 296), ([14, 16, 20, 34, 40, 56], 62, 297), ([15], 62, 298), ([18, 48, 60], 62, 299), ([7, 17, 31, 37, 49, 59], 62, 300), ([30], 62, 301), ([9, 45, 51], 62, 302), ([10, 34, 46], 62, 303), ([27, 33, 63], 62, 304), ([12, 42, 48, 54], 62, 305), ([25, 43], 62, 306), ([0, 24, 30], 63, 307), ([39, 45, 51], 63, 308), ([2, 28, 38, 40, 58], 63, 309), ([3, 27, 39], 63, 310), ([0, 42, 48], 64, 311), ([1, 5, 19, 35, 41, 55, 61], 64, 312), ([0, 36], 65, 313), ([3, 33, 45], 65, 314), ([2, 22, 32, 34, 38, 44, 52, 58, 64], 65, 315), ([33], 65, 316), ([0, 36, 66], 66, 317), ([35, 41, 49, 55, 61], 66, 318), ([12, 48], 66, 319), ([27, 39, 63], 66, 320), ([10, 28, 38, 52, 58], 66, 321), ([9, 15, 45, 51], 66, 322), ([30, 60, 66], 66, 323), ([7, 13, 43, 55], 66, 324), ([12, 42, 48, 54], 66, 325), ([33, 57, 63], 66, 326), ([10, 20, 46, 56], 66, 327), ([21, 45, 51], 66, 328), ([18, 60], 66, 329), ([17, 19, 23, 37, 49, 53, 59, 67], 66, 330), ([0, 18, 48], 67, 331), ([15, 21, 51], 67, 332), ([16, 20, 26, 40, 50, 56, 64], 67, 333), ([3, 63], 67, 334), ([18, 24, 54, 66], 67, 335), ([23, 43, 53, 65], 67, 336), ([0, 30, 60], 68, 337), ([21, 45], 68, 338), ([8, 28, 58, 62], 68, 339), ([9, 27, 33, 57, 69], 68, 340), ([48, 60], 68, 341), ([5, 11, 25, 31, 59], 68, 342), ([6, 30, 36, 66], 68, 343), ([], 68, 344), ([8, 14, 28, 34, 38, 52, 64], 68, 345), ([33, 63], 68, 346), ([0, 36, 54], 69, 347), ([1, 11, 31, 35, 41], 69, 348), ([0, 18], 70, 349), ([3, 33, 39, 69], 70, 350), ([2, 38, 58, 68, 70], 70, 351), ([15, 21, 45, 69], 70, 352), ([0, 6, 36], 71, 353), ([5, 43, 47], 71, 354), ([18, 24, 42], 71, 355), ([3, 45, 63], 71, 356), ([10, 26, 40, 44, 64], 71, 357), ([9, 21, 51], 71, 358), ([0, 42], 72, 359), ([7, 13, 23, 29, 49], 72, 360), ([12, 48], 72, 361), ([69], 72, 362), ([4, 10, 16, 26, 46, 56, 70], 72, 363), ([15, 33, 57], 72, 364)]\n",
      "([9], 8, 22)\n",
      "([9], 9, 28)\n",
      "([15], 14, 46)\n",
      "([], 68, 344)\n"
     ]
    }
   ],
   "source": [
    "def golds(n):\n",
    "    return [g for g in range(0,prime_pi(n)+2) if (is_prime(n-g) and is_prime(n+g))]\n",
    "\n",
    "#the slow algorithm to give glod(n): min non-negative integer make both `n-g` and `n+g` are primes\n",
    "def gold(n):\n",
    "    g=0\n",
    "    while not((is_prime(n-g) and is_prime(n+g))):\n",
    "        g+=1\n",
    "    return g\n",
    "\n",
    "\n",
    "\"\"\"\n",
    "return (g,step)\n",
    "  g:the min non-negative integer make both `n-g` and `n+g` are primes\n",
    "  step: the times of calling next_prime\n",
    "\"\"\"\n",
    "def xgold(n):\n",
    "    g,step=0,0\n",
    "    p,q=n,n\n",
    "    while not is_prime(p):\n",
    "        step+=1\n",
    "        q=next_prime(q)\n",
    "        g=q-n\n",
    "        p=n-g\n",
    "    return (g,step)\n",
    "\n",
    "\n",
    "golds_list=[(golds(n),prime_pi(n),n) for n in range(2,365) ]\n",
    "print(golds_list)\n",
    "for x in golds_list:\n",
    "    if not x[0] or (x[0][0]>=x[1]):\n",
    "        print(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "656c04cd3003474d98605c84cbd62505",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "SW50ZXJhY3RpdmUgZnVuY3Rpb24gPGZ1bmN0aW9uIGNoZWNrX0ltcHJvdmVkX0dvbGRiYWNoX0NvbmplY3R1cmUgYXQgMHg3ZjY0MzBmM2NlZDg+IHdpdGggMSB3aWRnZXQKICBuOiBTZWxlY3TigKY=\n"
      ]
     },
     "execution_count": 2,
     "metadata": {
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# check Improved Goldbach's Conjecture\n",
    "@interact\n",
    "def check_Improved_Goldbach_Conjecture(n=(2..1024)):\n",
    "    print (xgold(n),prime_pi(n),sigma(n,0),prime_pi(prime_pi(n)+n))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(344, (75, 13), 68, 8)\n",
      "(2, (0, 0), 1, 2)\n",
      "(3, (0, 0), 2, 2)\n",
      "(4, (1, 1), 2, 3)\n",
      "(6, (1, 1), 3, 4)\n",
      "(8, (3, 1), 4, 4)\n",
      "(10, (3, 2), 4, 4)\n",
      "(14, (3, 1), 6, 4)\n",
      "(16, (3, 2), 6, 5)\n",
      "(20, (3, 1), 8, 6)\n",
      "(22, (9, 3), 8, 4)\n",
      "(28, (9, 3), 9, 6)\n",
      "(32, (9, 2), 11, 6)\n",
      "(38, (9, 3), 12, 4)\n",
      "(46, (15, 4), 14, 4)\n",
      "(58, (15, 5), 16, 4)\n",
      "(68, (15, 4), 19, 6)\n",
      "(74, (15, 3), 21, 4)\n",
      "(82, (15, 3), 22, 4)\n",
      "(94, (15, 5), 24, 4)\n",
      "(112, (15, 2), 29, 10)\n",
      "(116, (15, 2), 30, 6)\n",
      "(121, (18, 4), 30, 3)\n",
      "(128, (21, 4), 31, 8)\n",
      "(130, (21, 5), 31, 8)\n",
      "(136, (27, 6), 32, 8)\n",
      "(146, (33, 7), 34, 4)\n",
      "(238, (39, 8), 51, 8)\n",
      "(265, (42, 7), 56, 4)\n",
      "(286, (45, 6), 61, 8)\n",
      "(341, (48, 9), 68, 4)\n",
      "(344, (75, 13), 68, 8)\n",
      "(496, (75, 11), 94, 10)\n",
      "(526, (87, 13), 99, 4)\n",
      "(904, (93, 14), 154, 8)\n",
      "(916, (93, 13), 156, 6)\n",
      "(1114, (117, 16), 186, 4)\n",
      "(1691, (120, 17), 263, 4)\n",
      "(1736, (135, 16), 270, 16)\n",
      "(1751, (138, 18), 272, 4)\n",
      "(1775, (138, 19), 274, 6)\n",
      "(1781, (168, 21), 275, 4)\n",
      "(2476, (183, 19), 366, 6)\n",
      "(3097, (210, 23), 442, 4)\n",
      "(3551, (228, 29), 497, 4)\n",
      "(5131, (300, 32), 685, 4)\n",
      "(8504, (333, 41), 1060, 8)\n",
      "(10342, (369, 37), 1269, 4)\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(18526, (393, 32), 2122, 8)\n",
      "(22564, (453, 46), 2521, 6)\n",
      "(24776, (525, 49), 2740, 16)\n",
      "(30728, (525, 54), 3315, 16)\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(40072, (621, 52), 4209, 8)\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(68707, (720, 63), 6828, 4)\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(125903, (810, 69), 11811, 4)\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(174913, (846, 61), 15909, 4)\n",
      "(181267, (1086, 92), 16434, 4)\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(371428, (1281, 94), 31629, 6)\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(827576, (1305, 94), 65990, 32)\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(936118, (1515, 106), 73910, 4)\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(1054141, (1590, 111), 82413, 8)\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(1159864, (1617, 119), 90020, 8)\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(1353559, (1722, 119), 103801, 4)\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(2591107, (1794, 120), 189274, 4)\n"
     ]
    }
   ],
   "source": [
    "# sage verify.sage\n",
    "\n",
    "# verify Improved Goldbach's Conjecture\n",
    "n=344\n",
    "g,step=xgold(n)\n",
    "print(n,xgold(n),prime_pi(n),sigma(n,0),prime_pi(prime_pi(n)+n))\n",
    "\n",
    "n=2\n",
    "g,step=xgold(n)\n",
    "peak=g\n",
    "while peak<1794:\n",
    "    if(g>=peak):\n",
    "        peak=g\n",
    "        print(n,(g,step),prime_pi(n),sigma(n,0),prime_pi(prime_pi(n)+n))\n",
    "    n+=1\n",
    "    g,step=xgold(n)"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "~/github/playmath/stage12-Goldbach Conjecture$ sage verify.sage\n",
    "(344, (75, 13), 68)\n",
    "(344, (75, 13))\n",
    "(496, (75, 11))\n",
    "(526, (87, 13))\n",
    "(904, (93, 14))\n",
    "(916, (93, 13))\n",
    "(1114, (117, 16))\n",
    "(1691, (120, 17))\n",
    "(1736, (135, 16))\n",
    "(1751, (138, 18))\n",
    "(1775, (138, 19))\n",
    "(1781, (168, 21))\n",
    "(2476, (183, 19))\n",
    "(3097, (210, 23))\n",
    "(3551, (228, 29))\n",
    "(5131, (300, 32))\n",
    "(8504, (333, 41))\n",
    "(10342, (369, 37))\n",
    "(18526, (393, 32))\n",
    "(22564, (453, 46))\n",
    "(24776, (525, 49))\n",
    "(30728, (525, 54))\n",
    "(40072, (621, 52))\n",
    "(68707, (720, 63))\n",
    "(125903, (810, 69))\n",
    "(174913, (846, 61))\n",
    "(181267, (1086, 92))\n",
    "(371428, (1281, 94))\n",
    "(827576, (1305, 94))\n",
    "(936118, (1515, 106))\n",
    "(1054141, (1590, 111))\n",
    "(1159864, (1617, 119))\n",
    "(1353559, (1722, 119))\n",
    "(2591107, (1794, 120))\n",
    "(3759164, (1833, 109))\n",
    "(5454062, (1851, 111))\n",
    "(5969581, (2010, 127))\n",
    "(6363983, (2064, 135))\n",
    "(6639736, (2085, 149))\n",
    "(6791669, (2112, 142))\n",
    "(7183186, (2217, 153))\n",
    "(9122719, (2352, 136))\n",
    "(10344379, (2352, 123))\n",
    "(10786495, (2754, 153))\n",
    "(23848807, (2784, 153))\n",
    "(27072352, (3339, 201))\n",
    "(46330868, (3429, 190))\n",
    "(57989356, (4395, 226))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "[ImprovedGoldbachConjecture.java](ImprovedGoldbachConjecture.java): a Java GUI to search gold(n) in range(n,n+256) by using BigInteger.isProbablePrime(64)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "## a simple and clear proof to Goldbach's Conjecture：gold(n) < prime_pi(prime_pi(n)+n)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "Today(2019-09-01) morning, I discovered this beautiful inequality below, which shows Goldbach's Conjecture holds true for any integer n>2.\n",
    "\n",
    "**Goldbach Conjecture Inequality 1**: **`gold(n) < prime_pi(n)+sigma(n,0)`**  \n",
    "gold(n): the min non-negative integer makes that both `n-g` and `n+g` are primes  \n",
    "prime_pi(n): the count of primes in 1..n  \n",
    "sigma(n,0): the count of n.divisors()  \n",
    "\n",
    "**`gold(n) < prime_pi(n), while n>344`**  \n",
    "**`gold(n) < prime_pi(n)*4395/3449751 ≈ prime_pi(n)*0.0013, while n>57989356`**\n",
    "\n",
    "2019-09-02 dawn, I found:  \n",
    "**Goldbach Conjecture Inequality 2**: **`gold(n) < prime_pi(prime_pi(n)+n)`**  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "These two inequalities are so straightforward, which directly show you the proving process. Let's prove **Inequality 2**, start from\n",
    "\n",
    "**Prime Gap Inequality**: ** p[i+1]-p[i]<=i ** , the i-th prime gap is less than or equal to `i`, i=1,2,3,... , here p[i]=nth_prime(i)  \n",
    "This is because we can dispatch distinct prime factors for `range(p[i],p[i+1])`, the items of the range is `[p[i],p[i]+1,p[i+2], ..., p[i+1]-1]`  \n",
    "Pigeonhole Principle shows `p[i+1]-p[i]<=i`, in other word, `next_prime(n)-n <= prime_pi(n)`  \n",
    "so, `p[i]<=i-1 + i-2+...+1+p[1] = 2+i*(i-1)/2`\n",
    "\n",
    "for example:\n",
    "<pre>\n",
    "i p[i] \n",
    "9 23 [23, 24, 25, 26, 27, 28]\n",
    "    [23,  2,  5,  13, 3,  7]\n",
    "</pre>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "\n",
    "Now, suppose $n>6$, and $n$ is composite, $factor(n) = p_1^{{\\alpha _1}}p_2^{{\\alpha _2}}...p_r^{{\\alpha _r}}$ ,\n",
    "$sigma(n,0)=({\\alpha _1}+1)*({\\alpha _2}+1)...*({\\alpha _r}+1)$  \n",
    "the number of primes less than $n$ and coprime with $n$ is $j$, suppose they are $[q_1,q_2,...,q_j]$  \n",
    "then we have `prime_pi(n) = r+j`  ,\n",
    "\n",
    "consider $[(n-1,n+1), (n-2,n+2),...,(n-x,n+x)]$ , for `x=1,2,3,...g`, until we get a prime pair `(n+g,n-g)`  \n",
    "Now, we must can dispatch distinct prime factors for each item. Put it another way, to dispatch distinct prime factors for `(n-x)*(n+x)` . Prime Gap Inequality ensures these prime be not great than `prime_pi(n)+n` . Pigeonhole Principle guarantees `len(s)<=prime_pi(prime_pi(n)+n)`, so\n",
    "\n",
    "    gold(n) < prime_pi(prime_pi(n)+n)\n",
    "\n",
    "and, `2n= (n-g) + (n+g)`, Goldbach Conjecture is proved!□\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "b9411b0eeb28412683f54192f8c9f0a3",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "SW50ZXJhY3RpdmUgZnVuY3Rpb24gPGZ1bmN0aW9uIHByb3ZlMl9nb2xkYmFjaF9jb25qZWN0dXJlIGF0IDB4N2Y2NDMwZjQ3MGM4PiB3aXRoIDEgd2lkZ2V0CiAgbjogRXZhbFRleHQodmFsdWXigKY=\n"
      ]
     },
     "execution_count": 3,
     "metadata": {
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "@interact\n",
    "def prove2_goldbach_conjecture(n=input_box(default=344)):\n",
    "    print('factor(n)=',factor(n))\n",
    "    p,q=n,n\n",
    "    x=0\n",
    "    s,factor_list=[],[]\n",
    "    while not (is_prime(p) and is_prime(q)):\n",
    "        x+=1\n",
    "        p-=1 #p=n-x\n",
    "        q+=1 #q=n+x\n",
    "        s.append((p,q))\n",
    "        factor_list.append((factor(p),factor(q)))\n",
    "\n",
    "    print(s)\n",
    "    print(factor_list)\n",
    "    print(n,p,q)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "Now, I am trying to prove **Inequality 1: gold(n) < prime_pi(n)+sigma(n,0)**\n",
    "\n",
    "step 1. construct a list `sig_list`,\n",
    "```\n",
    "    p,q=n,n\n",
    "    x=0\n",
    "    sig_list=[]\n",
    "    prev=n\n",
    "    while not is_prime(p):\n",
    "        x+=1\n",
    "        q+=1 #q=n+x\n",
    "        if is_prime(q):\n",
    "            p=n-x\n",
    "            if is_prime(p): \n",
    "                sig_list.append(p)\n",
    "            else: \n",
    "                prev=previous_prime(prev)\n",
    "                sig_list.append(prev)\n",
    "        else:\n",
    "            sig_list.append(q)\n",
    "```\n",
    "\n",
    "step 2. to drop `sigma(n,0)` items in `sig_list`, let `target_list` is the rest list. Which items to pick out? For every divisor which formed of $p_x^{{\\alpha _x}}...p_y^{{\\alpha _y}}$,choose one item which formed of $k *p_x^{{\\alpha _x}}...p_y^{{\\alpha _y}}$ to drop, and keep `k` contains as more different prime factors as possible. This means always do not drop `n-x`(which has been marked as previous_prime(n,?) in `sig_list`) but drop `n+x` which contains most different prime factors.\n",
    "\n",
    "step 3. Now, we must can dispatch distinct prime factors for each item of `target_list`, Pigeonhole Principle guarantees `len(target_list)<=prime_pi(n)`.\n",
    "so we have,\n",
    "\n",
    "       `gold(n) < prime_pi(n)+sigma(n,0)`  \n",
    "Goldbach Conjecture is proved!□\n",
    "\n",
    "for example:\n",
    "<pre>\n",
    "n=22\n",
    "('factor(n)=', 2 * 11, 'sigma(n,0)=', 4)\n",
    "('sig_list:', [19, 24, 25, 26, 27, 28, 17, 30, 13])\n",
    "('target_list:', [(19, 2), (17, 2), (13, 2), (5^2, 3), (2 * 13, 4)])\n",
    "assert tuple[0] of target_list has distinct primes!\n",
    "(22, 13, 31)\n",
    "\n",
    "\n",
    "n=46=2*23, sigma(46,0)=4\n",
    "('factor(n)=', 2 * 23)\n",
    "('sig_list:', [43, 48, 49, 50, 51, 52, 41, 54, 55, 56, 57, 58, 37, 60, 31])\n",
    "('target_list:', [(43, 2), (41, 2), (37, 2), (31, 2), (7^2, 3), (3 * 17, 4), (5 * 11, 4), (3 * 19, 4), (2 * 29, 4), (2 * 5^2, 6), (2^2 * 13, 6)])\n",
    "assert tuple[0] of target_list has distinct primes!\n",
    "(46, 31, 61)\n",
    "\n",
    "n=28\n",
    "('factor(n)=', 2^2 * 7, 'sigma(n,0)=', 6)\n",
    "('sig_list:', [23, 30, 19, 32, 33, 34, 35, 36, 19])\n",
    "('target_list:', [(23, 2), (19, 2), (19, 2)])\n",
    "assert tuple[0] of target_list has distinct primes!\n",
    "(28, 19, 37)\n",
    "\"\"\"here 19 occurs twice, since 19 is just `n-g`,the last item of sig_list, so it doesn't matter!)\"\"\"\n",
    "</pre>\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "a111f5ced4d145269ab98591b34e0756",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "SW50ZXJhY3RpdmUgZnVuY3Rpb24gPGZ1bmN0aW9uIHByb3ZlMV9nb2xkYmFjaF9jb25qZWN0dXJlIGF0IDB4N2Y2NDMwZjQ3NzU4PiB3aXRoIDEgd2lkZ2V0CiAgbjogRXZhbFRleHQodmFsdWXigKY=\n"
      ]
     },
     "execution_count": 5,
     "metadata": {
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "@interact\n",
    "def prove1_goldbach_conjecture(n=input_box(default=46)):\n",
    "    print('factor(n)=',factor(n),'sigma(n,0)=',sigma(n,0))\n",
    "    p,q=n,n\n",
    "    x=0\n",
    "    sig_list=[]\n",
    "    prev=n\n",
    "    while not is_prime(p):\n",
    "        x+=1\n",
    "        q+=1 #q=n+x\n",
    "        if is_prime(q):\n",
    "            p=n-x # p=2*n-q\n",
    "            if is_prime(p):\n",
    "                sig_list.append(p)\n",
    "                break\n",
    "            else:\n",
    "                prev=previous_prime(prev)\n",
    "                sig_list.append(prev)\n",
    "        else:\n",
    "            sig_list.append(q)\n",
    "\n",
    "    print('sig_list:',sig_list)\n",
    "    target_list=[(factor(item),sigma(item,0)) for item in sig_list]\n",
    "    target_list=sorted(target_list,key=lambda x: x[1],)\n",
    "    target_list=target_list[:-sigma(n,0)]\n",
    "    print('target_list:',target_list)\n",
    "    print('assert tuple[0] of target_list has distinct primes!')\n",
    "\n",
    "    print(n,p,q)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "## experiments zone"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[23, 24, 25, 26, 27, 28]"
      ]
     },
     "execution_count": 6,
     "metadata": {
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "p=lambda i:nth_prime(i)\n",
    "i=9\n",
    "range(p(i),p(i+1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "80"
      ]
     },
     "execution_count": 21,
     "metadata": {
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "n=344\n",
    "prime_pi(n+prime_pi(n))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "## **Glodbach Triangle**: `GT[i-2,j-2]:= (nth_prime(i)+nth_prime(j))//2 , i>=j>=2`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[3]\n",
      "[4, 5]\n",
      "[5, 6, 7]\n",
      "[7, 8, 9, 11]\n",
      "[8, 9, 10, 12, 13]\n",
      "[10, 11, 12, 14, 15, 17]\n",
      "[11, 12, 13, 15, 16, 18, 19]\n",
      "[13, 14, 15, 17, 18, 20, 21, 23]\n",
      "[16, 17, 18, 20, 21, 23, 24, 26, 29]\n",
      "[17, 18, 19, 21, 22, 24, 25, 27, 30, 31]\n",
      "[20, 21, 22, 24, 25, 27, 28, 30, 33, 34, 37]\n",
      "[22, 23, 24, 26, 27, 29, 30, 32, 35, 36, 39, 41]\n",
      "[23, 24, 25, 27, 28, 30, 31, 33, 36, 37, 40, 42, 43]\n",
      "[25, 26, 27, 29, 30, 32, 33, 35, 38, 39, 42, 44, 45, 47]\n",
      "[28, 29, 30, 32, 33, 35, 36, 38, 41, 42, 45, 47, 48, 50, 53]\n",
      "[31, 32, 33, 35, 36, 38, 39, 41, 44, 45, 48, 50, 51, 53, 56, 59]\n",
      "[32, 33, 34, 36, 37, 39, 40, 42, 45, 46, 49, 51, 52, 54, 57, 60, 61]\n",
      "[35, 36, 37, 39, 40, 42, 43, 45, 48, 49, 52, 54, 55, 57, 60, 63, 64, 67]\n",
      "[37, 38, 39, 41, 42, 44, 45, 47, 50, 51, 54, 56, 57, 59, 62, 65, 66, 69, 71]\n",
      "[38, 39, 40, 42, 43, 45, 46, 48, 51, 52, 55, 57, 58, 60, 63, 66, 67, 70, 72, 73]\n",
      "[41, 42, 43, 45, 46, 48, 49, 51, 54, 55, 58, 60, 61, 63, 66, 69, 70, 73, 75, 76, 79]\n",
      "[43, 44, 45, 47, 48, 50, 51, 53, 56, 57, 60, 62, 63, 65, 68, 71, 72, 75, 77, 78, 81, 83]\n",
      "[46, 47, 48, 50, 51, 53, 54, 56, 59, 60, 63, 65, 66, 68, 71, 74, 75, 78, 80, 81, 84, 86, 89]\n"
     ]
    }
   ],
   "source": [
    "n=25\n",
    "GT=[]\n",
    "for i in range(2,n):\n",
    "    row=[(nth_prime(i)+nth_prime(j))//2  for j in range(2,i+1)]\n",
    "    GT.append(row)\n",
    "    print(row)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
   ],
   "source": [
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath (stable)",
   "language": "sagemath",
   "metadata": {
    "cocalc": {
     "description": "Open-source mathematical software system",
     "priority": 10,
     "url": "https://www.sagemath.org/"
    }
   },
   "name": "sagemath"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.15"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}